#ifdef debug
// bfs-图像渲染
class Solution 
{   
    using PII = pair<int,int>; 
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
    {
        int flag = image[sr][sc]; // 记录初始像素点
        if(flag == color) return image; // 边界条件：如果要修改的像素点和目标像素点一致，那就直接返回
        int m = image.size(), n = image[0].size();
        std::queue<PII> q; // 用来保存每一次遍历的其实位置
        q.emplace(sr, sc); // 将起始位置添加到队列中

        while(!q.empty()) {
            auto[a,b] = q.front();
            image[a][b] = color;
            q.pop();

            for(int i=0; i<4; i++) {
                int x = a + dx[i], y = b + dy[i];
                if(x >=0 && x < m && y >= 0 && y < n && image[x][y] == flag) {
                    q.emplace(x, y);
                }
            }
        }
        return image;
    }
};

// bfs-岛屿数量
class Solution {
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    using PII = pair<int, int>;

public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        // bool vis[m][n] = {false};
        std::vector<std::vector<bool>> vis(m, std::vector<bool>(n));
        int num_island = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j] == false && grid[i][j] == '1') {
                    // 找到了1，开始进行广度优先遍历
                    num_island++;
                    std::queue<pair<int, int>> q;
                    q.emplace(i, j);
                    vis[i][j] = true;
                    while (!q.empty()) {
                        auto [a, b] = q.front();
                        q.pop();
                        // 遍历以ab为起点的上下左右四个方向
                        for (int t = 0; t < 4; t++) {
                            int x = a + dx[t], y = b + dy[t];
                            if (x >= 0 && x < m && y >= 0 && y < n &&
                                vis[x][y] == false && grid[x][y] == '1') {
                                q.emplace(x, y);
                                vis[x][y] = true;
                            }
                        }
                    }
                }
            }
        }
        return num_island;
    }
};

// bfs-岛屿的最大面积
class Solution 
{
    using PII = pair<int, int>;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    bool vis[100][100] = {false};
    int m, n;
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        m = grid.size(), n = grid[0].size();
        int area = 0;

        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                // 找到一块陆地，开始进行bfs
                if(grid[i][j] == 1 && vis[i][j] == false)
                {
                    int tmp = bfs(grid, i, j);
                    area = std::max(tmp, area);
                }
            }
        }
        return area;
    }

    int bfs(vector<vector<int>>& grid, int i, int j)
    {        
        int count = 0;
        std::queue<PII> q;
        q.emplace(i, j);
        vis[i][j] = true;
        count++; // 将起始岛屿计算上

        while(!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();
            
            for(int k=0; k<4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if(x>=0 && x<m && y>=0 && y<n && vis[x][y] == false && grid[x][y] == 1)
                {
                    q.emplace(x, y);
                    vis[x][y] = true;
                    count++;
                }
            }
        }
        return count;
    }
};

// bfs-被围绕的区域
class Solution 
{
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    using PII = pair<int, int>;
    std::queue<PII> edge; // 用来存储边缘连通块的坐标
    int m, n;
public:
    void solve(vector<vector<char>>& board) 
    {
        m = board.size(), n = board[0].size();
        // 1.先处理四个边上的连通块，将其修改为无关字符
        for(int j=0; j<n; j++)
        {
            if(board[0][j] == 'O') bfs(board, 0, j);
            if(board[m-1][j] == 'O') bfs(board, m-1, j);
        }

        for(int i=1; i<m - 1; i++)
        {
            if(board[i][0] == 'O') bfs(board, i, 0);
            if(board[i][n-1] == 'O') bfs(board, i, n - 1);
        }

        // 2.将数组中仍为'O'的改为'X', 'y'的改为'O'
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(board[i][j] == 'y') board[i][j] = 'O';
                else board[i][j] = 'X';
            }
        }
    }

    void bfs(vector<vector<char>>& board, int i, int j)
    {
        std::queue<PII> q;
        q.emplace(i, j);
        board[i][j] = 'y';
        while(!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();
            for(int k=0; k<4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if(x>=0 && x<m && y>=0 && y<n && board[x][y] == 'O')
                {
                    q.emplace(x, y);
                    board[x][y] = 'y';
                }
            }
        }
    }
};

// bfs-路权为1，最短路径问题
class Solution 
{
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    using PII = std::pair<int, int>;
    bool visit[101][101] = {false};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) 
    {
        int m = maze.size(), n = maze[0].size();
        std::queue<PII> q;
        q.emplace(entrance[0], entrance[1]);
        visit[entrance[0]][entrance[1]] = true;
        int step = 0;

        while(!q.empty()) 
        {
            step++;
            int sz = q.size();
            for(int j=0; j<sz; j++)
            {
                auto [a, b] = q.front();
                q.pop();
                for(int i=0; i<4; i++) 
                {
                    int x = a + dx[i], y = b + dy[i];
                    if(x >=0 && x < m && y >= 0 && y < n && !visit[x][y] && maze[x][y] == '.') 
                    {
                        // 判断一下是否已经到达出口
                        if(x == 0 || x == m - 1 || y == 0 || y == n - 1) return step;
                        q.emplace(x, y);
                        visit[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};

// bfs-最短基因变化问题
class Solution 
{
    char type[4] = {'A', 'C', 'G', 'T'};
    std::unordered_set<std::string> visit;
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) 
    {
        std::queue<std::string> q;
        q.emplace(startGene);
        visit.emplace(startGene); // 将遍历过的基因进行标记，避免重复遍历
        std::unordered_set<std::string> b_search(bank.begin(), bank.end()); // 将基因库中的基因放入哈希表中，方便后序判断基因变换的结果是否有效
        int step = 0;
        
        while(!q.empty())
        {
            step++;
            // 让基因的每一位都发生一次变化，判断变化是否有效
            // 有效则添加到队列中
            int sz = q.size();
            for(int k=0; k<sz; k++)
            {
                auto tmp = q.front();
                q.pop();
                for(int i=0; i<8; i++) 
                {
                    std::string gene = tmp; // 枚举每一个位置的变化时，每一次都要从一个新的字符串开始
                    for(int j=0; j<4; j++)
                    {
                        gene[i] = type[j];
                        // 基因有效，并且还没有被标记过
                        if(b_search.find(gene) != b_search.end() 
                           && visit.find(gene) == visit.end())
                        {
                           if(gene == endGene) return step;
                            q.emplace(gene);
                            visit.emplace(gene);
                        }
                    }
                }
            }
        }
        return -1;
    }
}

// bfs-单词接龙
class Solution 
{
    std::string type = "abcdefghijklmnopqrstuvwxyz";
    std::unordered_set<std::string> vis;
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
    {
        // 1.将beginWord存入队列中
        std::queue<std::string> q;
        q.emplace(beginWord);
        vis.emplace(beginWord);// 将该单词进行标记，防止重复变化

        // 2.将单词表预处理为哈希表，方便查找
        std::unordered_set<std::string> wl(wordList.begin(), wordList.end());
        if(!wl.count(endWord)) return 0;

        // 3.进行bfs
        int ret = 0;
        while(!q.empty())
        {
            int sz = q.size();
            ret++;
            for(int i=0; i<sz; i++) // 每一层有多少个单词需要变换
            {
                std::string f = q.front();
                std::cout << f << std::endl;
                std::cout << ret << std::endl;
                q.pop();
                for(int j=0; j<beginWord.size(); j++) // 单词第几位
                {
                    std::string word = f;
                    for(int k=0; k<type.size(); k++) // 变化为什么字符
                    {
                        word[j] = type[k];
                        if(!vis.count(word) && wl.count(word))
                        {
                            // 这次变换是一次合法，且没有标记过的
                            if(word == endWord) return ret + 1;
                            vis.emplace(word);
                            q.emplace(word);
                        }
                    }
                }
            }
        }
        return 0;
    }
};

// bfs-为高尔夫球比赛砍树
class Solution 
{
    using PII = std::pair<int, int>;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n;
public:
    int bfs(const PII &dst, const PII &src, vector<vector<int>>& forest)
    {
        // 如果当前位置就是最矮的，直接砍，返回0
        if(dst == src) return 0;

        std::queue<PII> q;
        bool vis[51][51] = {false}; // 用来标记位置是否被访问过, 避免走回头路
        q.emplace(src);
        vis[src.first][src.second] = true;
        
        int ret = 0;
        while(!q.empty())
        {
            int sz = q.size();
            ret++;
            while(sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                for(int i=0; i<4; i++) 
                {
                    int x = a + dx[i], y = b + dy[i];
                    if(x>=0 && x<m && y>=0 && y<n && forest[x][y]>0 && !vis[x][y])
                    {
                        if(x ==dst.first && y == dst.second) 
                        {
                            return ret;
                        }
                        q.emplace(x, y);
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }

    int cutOffTree(vector<vector<int>>& forest) 
    {
        // 1.确定砍树顺序
        m = forest.size(), n = forest[0].size();
        std::vector<PII> order; 

        // 1.1 先将所有的下标存储起来， 只需要存储树的下标
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(forest[i][j] > 1)
                    order.emplace_back(i, j);
            }
        }
        // 1.2 对order进行排序，按照在forest中的高度来
        sort(order.begin(), order.end(), [&](const PII &a, const PII &b){
            return (forest[a.first][a.second] < forest[b.first][b.second]);
        });

        // 2. 按照顺序，查找到指定位置的最短路径
        int ret = 0;
        PII src = {0, 0};
        for(auto pos : order)
        {
            int n = bfs(pos, src, forest);
            if(n < 0) return -1;
            ret += n;
            src = pos;
        }
        return ret;
    }
};

// 多源bfs————01矩阵
class Solution 
{
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    using PII = pair<int, int>;
public: 
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) 
    {
        // 多源bfs问题-有若干个源点
        // 解决思路：将若干个源点，看作一个超级源点，然后进行bfs
        // 将若干个源点看作一个超级源点，本质上就是将所有的源点一次性都加入到队列中
        // 这样这些源点就会向外扩展一层，这样就会将离终点最远的给排除掉

        int m = mat.size(), n = mat[0].size();
        std::queue<PII> q;
        std::vector<std::vector<int>> ret(m, std::vector<int>(n, -1)); // 结果数组，同时起到vis、step、sz的作用
        // 如果在该题中，直接以1作为起点，找最近的0，就会导致不知道结果填到那个位置上。
        // 所以，我们这里采用正难则反，我们以0为起点，1为终点。
        // 这样，直接将结果填到1对应的位置即可。
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(0 == mat[i][j]) {
                    q.emplace(i, j);
                    ret[i][j] = 0;
                } 
            }
        }

        // 进行bfs
        while(!q.empty()) 
        {
            auto [a, b] = q.front();
            q.pop();
            for(int i=0; i<4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if(x>=0 && x<m && y>=0 && y<n && ret[x][y] == -1)
                {
                    ret[x][y] = ret[a][b] + 1;
                    q.emplace(x, y);
                }
            }
        }
        return ret;
    }
};

// 多源bfs————飞地的数量
class Solution 
{
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    using PII = pair<int, int>;
public:
    int numEnclaves(vector<vector<int>>& grid) 
    {
        int m = grid.size(), n = grid[0].size();
        std::queue<PII> q;
        std::vector<std::vector<int>> dist(m, std::vector<int>(n, -1));

        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if((i==0 || i==m-1 || j==0 || j==n-1)) {
                    if(grid[i][j] == 1) {
                        q.emplace(i, j);
                        dist[i][j] = 1;
                    }
                }
                if(0 == grid[i][j]) {
                    dist[i][j] = 0;
                }
            }
        }

        while(!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();
            for(int i=0; i<4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if(x>=0 && x<m && y>=0 && y<n && dist[x][y] == -1)
                {
                    if(grid[x][y] == 1) {
                        q.emplace(x, y);
                        dist[x][y] = dist[a][b] + 1;
                    }
                }
            }
        }

        int ret = 0;
        for(auto row : dist)
        {
            for(auto e : row)
            {
                if(e == -1) ret++;
            }
        }
        return ret;
    }
};

// 多源bfs————地图中的最高点
class Solution 
{
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    using PII = pair<int, int>;
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) 
    {
        int m = isWater.size(), n = isWater[0].size();
        std::queue<PII> q;
        std::vector<std::vector<int>> dist(m, std::vector<int>(n, -1));
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(isWater[i][j] == 1)
                {
                    // 将所有的水域格子的高度设置为0
                    // 并且将所有的水域格子作为超级源点，向外扩散陆地
                    q.emplace(i, j);
                    dist[i][j] = 0;
                }
            }
        }

        while(!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();
            for(int i=0; i<4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if(x>=0 && x<m && y>=0 && y<n && dist[x][y] == -1)
                {
                    // 扩散的位置合法，并且没有被遍历过
                    dist[x][y] = dist[a][b] + 1;
                    q.emplace(x, y);
                }
            }
        }
        return dist;
    }
};

// 多源bfs————地图分析
class Solution 
{
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    using PII = pair<int, int>;
public:
    int maxDistance(vector<vector<int>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        std::vector<std::vector<int>> dist(m, std::vector<int>(n, -1));
        std::queue<PII> q;
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(grid[i][j] == 1) {
                    // 将陆地作为超级源点
                    dist[i][j] = 0;
                    q.emplace(i, j);
                }
            }
        }

        while(!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();
            for(int i=0; i<4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if(x>=0 && x<m && y>=0 && y<n && dist[x][y] == -1)
                {
                    dist[x][y] = dist[a][b] + 1;
                    q.emplace(x, y);
                }
            }
        }
        int ret = -1;
        for(auto row : dist)
            for(auto e : row)
                ret = std::max(ret, e);
        return ret > 0 ? ret : -1;
    }
};

// bfs 解决拓扑排序————课程表
class Solution 
{
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
    {
        // 1. 建图
        std::unordered_map<int, std::vector<int>> edges;
        std::vector<int> in(numCourses); // 顶点的入度（下标表示顶点，值表示该顶点的入度）       
        for(auto row : prerequisites)
        {
            // row是一个数组[a, b]
            int a = row[0], b = row[1];
            edges[b].emplace_back(a);
            in[a]++;
        }

        // 2. 将所有入度为0的顶点加入到队列中
        std::queue<int> q;
        for(int i=0; i<numCourses; i++)
        {
            if(in[i] == 0) q.emplace(i);
        }

        // 3. bfs
        while(!q.empty())
        {
            int a = q.front();
            q.pop();
            // 将a指向的顶点的入度--
            for(auto e : edges[a])
            {
                in[e]--;
                if(in[e] == 0) q.emplace(e);
            }
        }

        // 4. 如果完成了一次拓扑排序，此时每一个顶点的入度应该都为0
        for(int &e : in)
            if(e) return false;
        return true;
    }
};

// bfs 解决拓扑排序————课程表2
class Solution 
{
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
    {
        // 1. 建图
        std::vector<std::vector<int>> edges(numCourses);
        std::vector<int> in(numCourses);// 顶点的入度
        for(auto &row : prerequisites)
        {
            int a = row[0], b = row[1];
            edges[b].emplace_back(a);
            in[a]++;
        }

        // 2. 将所有入度为0的点，加入到队列中
        std::queue<int> q;
        for(int i=0; i<numCourses; i++)
        {
            if(in[i] == 0) q.emplace(i);
        } 

        // 3. bfs
        std::vector<int> ret;
        while(!q.empty())
        {
            int a = q.front();
            q.pop();
            ret.emplace_back(a);
            // 将a连接的顶点的入度--
            for(int &e : edges[a])
            {
                in[e]--;
                if(in[e] == 0) q.emplace(e);
            }
        }
        
        // 4. 判断结果是否完整
        if(ret.size() == numCourses) return ret;
        return {};
    }
};
#endif

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <string>
#include <vector>

class Solution 
{
public:
    static std::string alienOrder(std::vector<std::string>& words) 
    {
        // 0. 初始化容器
        std::unordered_map<char, int> in_degree; // 入度
        // 初始化入度，遍历字典，将所有的字符的入度都初始化为0
        // 如果不进行初始化，直接收集信息建图，那么该入度表中，所有的入度都不为0
        for(auto &s : words)
            for(char c : s)
                in_degree.emplace(c, 0);
        std::unordered_map<char, std::unordered_set<char>> edges(in_degree.size());


        // 1. 收集信息 并 建图
        for(int i=0; i<words.size(); i++)
        {
            std::string front = words[i];
            for(int j=i+1; j<words.size(); j++)
            {
                std::string back = words[j];
                // 1.1 双指针
                for(int k=0; k<front.size(); k++) 
                {
                    if(k >= back.size()) return "";
                    if(front[k] != back[k]) 
                    {
                        if(!edges.count(front[k]) || !edges[front[k]].count(back[k])) {
                            edges[front[k]].emplace(back[k]);
                            in_degree[back[k]]++;
                        }
                        break;
                    }
                }
            }
        }
        
        for(auto &[k, v] : edges)
        {
            std::cout << k << "-> ";
            for(auto e : v)
            {
                std::cout << e << "";
            }
            std::cout << std::endl;
        }

        for(auto &[k, v] : in_degree)
            std::cout << k << " : " << v << std::endl;

        // 2. 将所有入度为0的字符加入队列中
        std::queue<char> q;
        for(auto &[c, in] : in_degree)
        {
            if(in == 0) q.emplace(c);
        }

        // 3. bfs
        std::string ans;
        while(!q.empty())
        {
            char c = q.front();
            q.pop();
            ans += c;
            // 将c字符所指向的字符的入度--
            for(auto k : edges[c]/*edges[c]是一个unordered_set*/)
            {
                in_degree[k]--;
                if(in_degree[k] == 0) q.emplace(k);
            }
        }
        return ans.size() == in_degree.size() ? ans : "";
    }
};

int main()
{
    std::vector<std::string> words({"wrt", "wrf", "er", "ett", "rftt"});    
    std::string ret = Solution::alienOrder(words);
    std::cout << ret << std::endl;
    return 0;
}